This invention relates to apparatus for shifting or rotating digital information and more particularly to a flow-through type shift/rotate circuit.
It is well known in the data processing art to provide data processing systems with means for shifting or rotating (circular shifting) multibit binary data. Shifting of data is typically required in performing certain arithmetic operations such as multiplication or division, while rotation of data is typically used in data field manipulation operations such as field extraction or insertion.
Prior art shift/rotate apparatus are generally of two types, namely the flow-through type which normally permits a shift operation or a rotate operation to be performed within a single time period of the processing unit and the shift register type in which the number of time periods of the processing unit required to complete a shift or a rotate operation depends on the number of positions shifted or rotated. In general, high operating speed is desirable in data processing systems. Therefore, the flow-through type shift/rotate apparatus which has a shorter execution time is preferred over the shift register type in high performance data processing systems.
It is believed that formerly, flow-through type shift/rotate apparatus have not been used in data processing systems fabricated on a single integrated circuit chip, i.e., microprocessor and microcomputers, primarily because the chip area limitations of the integrated circuit technologies used did not permit practical implementation of the highly complex prior art flow-through shift/rotate circuits. Thus, the chip area limitations dictated the use of the far simpler shift register type of shift/rotate circuit. Moreover, microprocessors and microcomputers have heretofore been designed primarily for relatively low performance applications. Therefore, the execution time of the shift register type of shift/rotate apparatus has been adequate for such applications.
Recent advances in integrated circuit technology in the area known as very large scale integration (VLSI) have made it possible to design microprocessors and microcomputer chips having a much greater number of components and capable of much higher performance. As such, the use of flow-through type shift/rotate circuit in such chips is now both desirable and practical. However, the chip area occupied by the shift/rotate circuit still has an important effect on the cost of the microprocessor or microcomputer in which it is used. In this respect, the prior art flow-through shift-rotate circuits are deficient in that they require a relatively large chip area for their implementation. Therefore, a need clearly exists for a flow-through type shift/rotate circuit which occupies a relatively small chip area when implemented in an integrated circuit.
Some prior art flow-through type shift/rotate circuits perform bidirectional (i.e., either right or left) shift or rotate operations using only a unidirectional shifter/rotator. A shift or a rotate operation in the opposite direction to that provided by the unidirectional shifter/rotator is performed by first reflecting (reversing the order of the bits) the data before passage through the shifter/rotator and reflecting the data again after passage through the shifter/rotator. Therefore, such prior art circuits require additional circuitry for performing the reflections on the data. One such prior art circuit uses a single data reflection circuit coupled to receive data from the unidirectional shifter/rotator and performs the shift or rotate operation in the opposite direction to that provided by the unidirectional shifter/rotator by making the data pass twice through both the shifter/rotator and the reflection circuit. From the standpoint of chip area, using a unidirectional shifter/rotator is advantageous because it occupies less chip area than a bidirectional shifter/rotator. However, in the case of the prior art circuits, the chip area savings derived from using a unidirectional shifter/rotator is more than cancelled by the addition of data reflection circuitry. Moreover, where the prior art circuit requires a double passage of the data, the execution time for a shift or rotate operation is also increased.
In another prior art flow-through type shift/rotate circuit, a bidirectional rotate circuit is combined with a vector mask generator and an appropriate gating network to provide a bidirectional shift/rotate circuit. For rotate operations, the mask generator is not used. However, for shift operations the output of the mask generator controls the gating network to provide masking of the circularly shifted bits of the data. This latter circuit configuration is advantageous in that it can be adapted to provide both the arithmetic shift operation as well as the logical shift operation. However, prior art bidirectional rotate circuits require a relatively large chip area for their implementation, although the mask generator may be implemented in a relatively small chip area. Therefore, a bidirectional rotate circuit occupying a small chip to be used in conjunction with a mask generator would be desirable. In particular it would be desirable to have a flow-through type circuit which provides bidirectional rotation of data using a unidirectional shifter/rotator but which requires neither reflection of the data nor multiple passes of the data through the circuit.